package compiler.parser;

import java.io.IOException;
import java.util.ArrayList;

import compiler.ast.*;
import compiler.ast.Number;
import compiler.scanner.LexicalException;
import compiler.scanner.Scanner;
import compiler.scanner.Token;
import compiler.symboltable.SymbolTable;
import compiler.symboltable.SymbolTable.ItemType;

public class Parser {
	private Scanner scanner;
	private Token current;
	
	public Parser(Scanner scanner) {
		this.scanner = scanner;
	}
	
	public ASTRoot parse() throws Exception {
		current = scanner.consume();
		
		SymbolTable root = new SymbolTable("root", null);
		root.addFuncItem("Output",null);
		root.addFuncItem("Input", null);
		Module module = module(root);
		
		return new ASTRoot(module);
	}
	
	/**
	 * just match a token, does not consume it
	 * @param Token to match
	 * @throws SyntacticException
	 */
	private void match(Token t) throws SyntacticException {
		if(current == t)
		{
			//System.out.printf("match:\t"+t.name()+"\n"); // DEBUG
		}
		else
			throw new SyntacticException(current.line(), current.position(), "'"+t.name().toLowerCase()+"'", current.value());
	}
	
	/**
	 * Token Match and consume it
	 * @param Token 当前所在的层次
	 * @throws LexicalException 
	 * @throws IOException
	 * @throws SyntacticException
	 * @return value of matched token
	 */
	private String consume(Token t) throws SyntacticException, LexicalException, IOException
	{
		if(current == t)
		{
			String ret = current.value();
			//System.out.printf("consume:\t"+t.name()+"\n"); // DEBUG
			current = scanner.consume();
			return ret;
		}
		else
			throw new SyntacticException(current.line(), current.position(), "'"+t.name().toLowerCase()+"'", current.value());
	}
	
	/**
	 * consume the current token only if it matches parameter token.
	 * @param Token optionally expected token
	 * @throws LexicalException 
	 * @throws IOException 
	 * @return value of matched token
	 */
	private String optional(Token t) throws LexicalException, IOException {
		if (current == t) {
			String ret = current.value();
			//System.out.printf("consume:\t"+t.name()+"\n"); // DEBUG
			current = scanner.consume();
			return ret;
		} else {
			return null;
		}
	}

	/* recursive decent parser functions */
	/**
	 * parse identifier
	 * @param scope
	 * @return
	 * @throws SyntacticException
	 * @throws LexicalException
	 * @throws IOException
	 * @throws SemanticException
	 */
	//private Identifier identifier() throws SyntacticException, LexicalException, IOException
	//{
	//	return new Identifier(consume(Token.Identifier));
	//}
	
	private Identifier identifier(SymbolTable scope, ItemType type) throws SyntacticException, LexicalException, IOException, SemanticException {
		match(Token.Identifier);
		
		String id = current.value();
		
		if (!scope.isValid(id)) {
			throw new SemanticException(current.line(), current.position(), "can't find '"+id+"' in scope '"+scope.getName()+"'.");
		}
		
		if (! scope.isType(id, type)) {
			throw new SemanticException(current.line(), current.position(), "type of variable '"+id+"' is not "+type.name()+".");
		}
		
		consume(Token.Identifier);
		
		return new Identifier(id);
	}

	private Identifier identifier(SymbolTable scope) throws SyntacticException, LexicalException, IOException, SemanticException {
		match(Token.Identifier);
		
		if (scope.isValid(current.value())) {
			throw new SemanticException(current.line(), current.position(), "variable '"+current.value()+"' already exists.");
		}
		
		String id = consume(Token.Identifier);
		return new Identifier(id);
	}
	
	private static final long MaxOfInt = 2147483647l;
	private static final long MinOfInt = -2147483648l;
	
	/**
	 * parse number
	 * @return
	 * @throws LexicalException
	 * @throws IOException
	 * @throws SyntacticException
	 * @throws SemanticException
	 */
	private Number number() throws LexicalException, IOException, SyntacticException, SemanticException {
		String sign = optional(Token.PlusMinus);
		match(Token.Number);
		
		String num = current.value();
		if (sign != null && sign.equals("-")) {
			num = sign + num;
		}
		
		long val = Long.parseLong(num); 
		
		if (val > MaxOfInt || val < MinOfInt) 
		{
			throw new SemanticException(current.line(), current.position(), "int number overflow!");		// 数字过大溢出
		}
		
		consume(Token.Number);
		
		return new Number((int) val);
	}
	
	/**
	 * parse designator
	 * @param scope
	 * @throws LexicalException 
	 * @throws IOException 
	 * @throws SyntacticException 
	 * @throws SemanticException 
	 */
	private Designator designator(SymbolTable scope) throws LexicalException, SyntacticException, IOException, SemanticException
	{
		Token next = scanner.peek();
		Identifier id;
		Expression expr = null;
		if (next == Token.SqrBracketL) {
			id = identifier(scope, ItemType.ARRAY);
			consume(Token.SqrBracketL);
			expr = expression(scope);
			consume(Token.SqrBracketR);
		} else {
			id = identifier(scope, ItemType.INT);
		}		

		return new Designator(id, expr);

	}
	/**
	 * parse factor
	 * @param scope
	 * @throws LexicalException 
	 * @throws IOException 
	 * @throws SyntacticException 
	 * @throws SemanticException 
	 * 
	 */
	private Factor factor(SymbolTable scope) throws IOException, LexicalException, SyntacticException, SemanticException
	{
		Factor ret;
		
		// FIRST(factor) = {ident, "+"/"-", number, "("}
		switch (current) {
		case Identifier:
			Token next = scanner.peek();
			switch (next) {
			case ParenL:
				ret = functionCall(scope);
				break;
			default:
				ret = designator(scope);
			}
			break;
		case PlusMinus:
		case Number:
			ret = number();
			break;
		case ParenL:
			consume(Token.ParenL);
			ret = expression(scope);
			consume(Token.ParenR);
			break;
		default:
			throw new SyntacticException(current.line(), current.position(), "identifier or '+'/'-' or number or '('", current.value());
		}
		
		return ret;
	}
	/**
	 * parse term
	 * @throws SemanticException 
	 * @throws IOException 
	 * @throws SyntacticException 
	 * @throws LexicalException 
	 * 
	 */
	private Term term(SymbolTable scope) throws SemanticException, LexicalException, SyntacticException, IOException
	{		//if(scanner.peek() == Token.Identifier)
		SignedFactor child = new SignedFactor('*', factor(scope));
		Term ret = new Term(child);
		String sign;
		while ((sign = optional(Token.MultDiv)) != null) {
			child = new SignedFactor(sign.charAt(0), factor(scope));
			ret.addFactor(child);
		}
		
		return ret;
	}
	/**
	 * parse expression
	 * @throws SemanticException 
	 * @throws IOException 
	 * @throws SyntacticException 
	 * @throws LexicalException 
	 */
	private Expression expression(SymbolTable scope) throws LexicalException, SyntacticException, IOException, SemanticException
	{
		Term child = term(scope);
		Expression ret = new Expression(child);
		String sign;
		while ((sign = optional(Token.PlusMinus)) != null) {
			child = term(scope);
			child.setSign(sign.charAt(0));
			ret.addTerm(child);
		}
		return ret;
	}
	/**
	 * parse relationFUNC
	 * 
	 */
	private Relation relation(SymbolTable scope) throws LexicalException, SyntacticException, IOException, SemanticException
	{
		Expression left = expression(scope);
		String oprt = consume(Token.RelOpr);
		Expression right = expression(scope);
		
		return new Relation(oprt, left, right);
	}
	/**
	 * parse assignment
	 * 
	 */
	private Assignment assignment(SymbolTable scope) throws LexicalException, SyntacticException, IOException, SemanticException
	{
		Designator desg = designator(scope);
		consume(Token.Assign);
		Expression expr = expression(scope);
		
		return new Assignment(desg, expr);
	}
	/**
	 * parse functioncall
	 * 
	 */
	private FunctionCall functionCall(SymbolTable scope) throws LexicalException, SyntacticException, IOException, SemanticException
	{
		Identifier ident = identifier(scope, ItemType.FUNC);
		FunctionCall ret = new FunctionCall(ident);
		
		consume(Token.ParenL);
		if (optional(Token.ParenR) == null) {
			Expression arg = expression(scope);
			ret.addParam(arg);
			while (optional(Token.Comma) != null) {
				arg = expression(scope);
				ret.addParam(arg);
			}
			consume(Token.ParenR);
		}
		
		return ret;	
	}
	/**
	 * parse ifstatement
	 * @return 
	 * 
	 */
	private IfStatement ifStatement(SymbolTable scope) throws LexicalException, SyntacticException, IOException, SemanticException
	{
		consume(Token.If);
		consume(Token.ParenL);
		Relation rel = relation(scope);
		consume(Token.ParenR);
		consume(Token.Then);
		ArrayList<Statement> bodyT = null;
		if(current!=Token.Else && current != Token.End)
		{
			bodyT = stateSequence(scope);
		}
		ArrayList<Statement> bodyF = null;
		if (optional(Token.Else) != null) {
		
			//if(current != Token.End)
				bodyF = stateSequence(scope);
		}
		consume(Token.End);
		
		return new IfStatement(rel, bodyT, bodyF);
	}
	/**
	 * parse whileStatement
	 * 
	 */
	private WhileStatement whileStatement(SymbolTable scope) throws LexicalException, SyntacticException, SemanticException, IOException
	{
		consume(Token.While);
		consume(Token.ParenL);
		Relation rel = relation(scope);
		consume(Token.ParenR);
		consume(Token.Do);
		ArrayList<Statement> body = null;
		//if(current != Token.End)
			body = stateSequence(scope);
		consume(Token.End);
		
		return new WhileStatement(rel, body);
	}
	/**t
	 * parse returnStatement
	 * @return 
	 * 
	 */
	private ReturnStatement returnStatement(SymbolTable scope) throws LexicalException, SyntacticException, SemanticException, IOException
	{
		consume(Token.Return);
		
		// FOLLOW(returnStatement) = {";", "end", "else"}
		if (current == Token.Semicolon || current == Token.End || current == Token.Else) {
			return new ReturnStatement(null);
		} else {
			Expression expr = expression(scope);
			return new ReturnStatement(expr);
		}
		
	}
	/**t
	 * parse statement
	 * @return 
	 * 
	 */
	private Statement statement(SymbolTable scope) throws LexicalException, SyntacticException, SemanticException, IOException
	{
		Statement ret;
		
		// FIRST(statement) = {ident, "if", "while", "return"}
		switch (current) {
		case Identifier:
			Token next = scanner.peek();
			switch (next) {
			case ParenL:
				ret = functionCall(scope);
				break;
			default:
				ret = assignment(scope);
			}
			break;
		case If:
			ret = ifStatement(scope);
			break;
		case While:
			ret = whileStatement(scope);
			break;
		case Return:
			ret = returnStatement(scope);
			break;
		default:
			throw new SyntacticException(current.line(), current.position(), "identifier or 'if' or 'while' or 'return'", current.value());
		}
		
		return ret;
	}
	/**
	 * parse stateSequence
	 * @return 
	 * 
	 */
	private ArrayList<Statement> stateSequence(SymbolTable scope) throws LexicalException, SyntacticException, SemanticException, IOException
	{

		ArrayList<Statement> ret = new ArrayList<Statement>();
		Statement stmt = statement(scope);
		ret.add(stmt);
		
		while (optional(Token.Semicolon) != null) {
				stmt = statement(scope);
				ret.add(stmt);	
		}
		
		return ret;
	}
	/**
	 * parse type
	 * 
	 */
	//private void type() throws LexicalException, SyntacticException, IOException
	//{
		//if(scanner.peek() == Token.Identifier)
			
	//}
	/**
	 * parse varDeclaration
	 * @throws Exception 
	 * 
	 */
	private void varDeclaration(SymbolTable scope) throws Exception
	{
		consume(Token.Var);
		while(current == Token.Identifier)
		{
			int size = scope.size();

			scope.addIntItem(current.value());
			
			consume(Token.Identifier);

			while(optional(Token.Comma)!=null)
			{	
				scope.addIntItem(current.value());
				consume(Token.Identifier);
			}
			consume(Token.Colon);

			if(current == Token.Integer)
			{
				consume(Token.Integer);
				consume(Token.Semicolon);
			}
			else if(current == Token.Array)
			{
				consume(Token.Array);
				int len = number().getValue();
				consume(Token.Of);
				consume(Token.Integer);
				consume(Token.Semicolon);
				for(int i = size; i < scope.size(); i ++)
				{	
					scope.get(i).setType(ItemType.ARRAY);
					scope.get(i).setLength(len);
				}

			}
			else {
				throw new SyntacticException(current.line(),current.position(),Token.Integer.name()+
						" or "+Token.Array.name(),current.name());
			}
		}		
	}
	/**
	 * parse funcDeclaration
	 * @throws Exception 
	 * 
	 */
	private FuncDeclaration funcDeclaration(SymbolTable scope) throws Exception
	{	
		
		boolean isfunc = (consume(Token.FuncProc).equals("function"));
		String funcname = current.value();	
		SymbolTable t = new SymbolTable(funcname, scope);
		//scope.addFuncItem(current.value(),current.line(),current.position(),t);
		
		Identifier id = identifier(scope);
		FuncDeclaration n = new FuncDeclaration(id);
		scope.addFuncItem(funcname,t);
		n.setIsFunc(isfunc);
		
		ArrayList<Identifier> params = new ArrayList<Identifier>();
		
		if(optional(Token.ParenL)!=null)
		{
			if(current == Token.Identifier)
			{
				t.addParamItem(current.value());
				params.add(new Identifier(current.value()));
				consume(Token.Identifier);
				while(optional(Token.Comma)!=null)
				{
					t.addParamItem(current.value());
					params.add(new Identifier(current.value()));
					consume(Token.Identifier);
				}
			}
			consume(Token.ParenR);
		}
		n.setParamList(params);
		
		consume(Token.Semicolon);
		if(current == Token.Var)
			varDeclaration(t);
		consume(Token.Begin);
		if(current == Token.Identifier || 
				   current == Token.If || 
			    current == Token.While ||
			    current == Token.Return)
		{
			n.setBody(stateSequence(t));
		}
		//n.getBody().add(returnStatement(scope,isfunc));
		//consume(Token.Return);
		//if(!isfunc)
		//	expression(scope);
		n.checkReturn(current.line(),current.position());
		//else if(!isfunc && current !)
		consume(Token.End);
		consume(Token.Identifier);
		consume(Token.Semicolon);
		
		//whether we should add params in the symboltable
		
		n.setLocalVars(t);
		
		return n;
	}
	
	/**
	 * parse module
	 * @throws Exception 
	 * 
	 */
	private Module module(SymbolTable scope) throws Exception
	{
		//if(scanner.peek() == Token.Identifier)
		consume(Token.Module);
		SymbolTable t = new SymbolTable(current.value(), scope);
		Identifier id = identifier(scope);
		
		Module m = new Module(id);
		
		ArrayList<FuncDeclaration> f = new ArrayList<FuncDeclaration>();
		consume(Token.Semicolon);
		if(current == Token.Var)
			varDeclaration(t);
		while(current == Token.FuncProc)
		{
			f.add(funcDeclaration(t));
		}
		m.setFuncs(f);
		consume(Token.Begin);
		
		if(current == Token.Identifier || 
				   current == Token.If || 
			    current == Token.While ||
		   current == Token.Return)
		{
			m.setBody(stateSequence(t));
		}
		consume(Token.End);
		consume(Token.Identifier);
		match(Token.Period);
		m.setVars(t);
		return m;
	}
	
	/* Test Methods */
	public void test0() throws IOException, LexicalException {
		Token t = scanner.consume();
		while (t != null) {
			System.out.println(t.toString());
			t = scanner.consume();
		}
	}
	
	public void test1() throws IOException, LexicalException {
		System.out.println("    Peeked Token\t|\tConsumed Token");
		
		Token t = scanner.peek();
		while (t != null) {
			System.out.print(t.toString() + "\t| ");
			System.out.println(scanner.consume().toString());
			t = scanner.peek();
		}
	}
	
	public void test2() throws IOException, LexicalException {
		Token t = scanner.consume();
		while (t != null) {
			switch (t) {
			case PlusMinus:
				Token tn = scanner.peek();
				if (tn == Token.Number) {
					String sign = (t.value() == "-") ? "-" : "";
					long n = Long.parseLong(sign+tn.value());
					System.out.println("A number detected: " + n);
					
					scanner.consume();
				} else {
					System.out.println(t.toString());
				}
				break;
			case Number:
				int n = Integer.valueOf(t.value());
				System.out.println("A number detected: " + n);
				break;
			default:
				System.out.println(t.toString());
			}
			t = scanner.consume();
		}
	}

}
